미로탐색 알고리즘_{(r1 문단 편집)}

=== [[다익스트라 알고리즘]] ===
||<tablealign=center> [youtube(lufECeWtN34)] ||
|| '''영화 Next의 인간 다익스트라 알고리즘(?)'''  ||
주어진 시작 지점에서 출구를 향하는 '''최단 경로'''를 찾아내는 알고리즘. 위의 BFS 알고리즘의 발전형이다. 사실 이 알고리즘은 특정 지점에서 특정 지점까지 가는 최단 경로 모두를 알아낼 수 있다. 하지만 단점은 최단 경로인 게 확인될 때까지 가능한 모든 경로를 테스트하기 때문에 아무래도 아래의 A* 알고리즘에 비해 성능이 몹시, 많이 떨어진다. 그래서 실시간 길찾기 알고리즘으로 다익스트라 알고리즘은 적절하지 않다.

다익스트라 알고리즘은 [[분신술]] 알고리즘이다. 초기값은 최단 경로 '''없음''', 최단 경로의 길이 '''[[무한대]]'''로 시작한다. 갈림길이 나타나면 미로를 탐색하는 탐색자(traveler)가 갈림길의 갯수만큼 분신을 만들어 각각의 길을 따라간다. 그리고 자신과 자신의 원본(부모 객체)이 지나간 길을 지워나간다. 그러다가 더 이상 갈 데가 없는 분신은 스스로 소멸한다. 만약 분신들 중 하나가 출구를 찾아냈다면 해당 분신과 그의 모든 원본들이 여행한 경로를 해답(최단 경로)에 기록하고 그 길이를 최단 경로로 설정한다. 그리고 모든 분신들에게 최단 길이를 '''방송'''하고 스스로는 소멸한다. 최단 길이보다 먼 길을 돌고 있는 분신들은 이 때 모두 소멸한다. 나중에라도 스스로의 여행 거리가 방송된 최단 거리를 넘어가면 스스로 소멸한다. 남아 있는 분신들 중 더 짧은 경로로 해답을 찾은 분신이 있다면 그 경로로 해답을 갱신하고 최단 길이를 또 방송한다. 그리고 다음 time step으로 이동. 이 과정을 모든 분신들이 없어질 때까지 반복. 모든 분신이 소멸하면 기록돼있는 최단 경로를 해답으로 제출한다. 만약 해답이 없다면 그 미로는 출구로 통하는 길이 없는 것이다.

기술적인 이유로 무한대 값을 설정할 수 없다면 충분히 큰 값을 설정해야 한다. 충분히 큰 값이 아닐 경우 해답이 존재하는 미로인데도 경로가 없다고 해답을 낸다. 초보가 저지르기 쉬운 실수로 초기값의 최단 길이를 0이나 -1로 넣는 게 있다. 이렇게 하면 다익스트라 알고리즘이 시작하자마자 끝나면서 '경로 없음'이라는 결과를 뱉기 때문에 엄한 델 디버깅하게 될 위험이 있다.[* [[C언어]]에서 unsigned int 자료형에 -1값을 대입하면 오버플로를 일으키면서 해당 자료형의 최대값이 자동 대입된다. 하지만 이건 트릭이고 컴파일러 경고를 받으므로 권장되지 않는다.]

다익스트라 알고리즘의 천적은 바로 완전 개방형 맵. 커다란(무한한) 빈 박스에 출발점과 도착점만 찍혀 있고 장애물이 전혀 없는 미로의 경우다. 이런 미로는 첫 최단 경로(직선 경로)를 찾아낼 때까지 출발점에서 그 거리에 비례하는 원형 탐색 공간을 소비한다. 최악의 경우는 도착점 주위에 벽이 둘러쳐져 있고(도달 불가능) 공간이 무한대인 맵이다. 이 경우 다익스트라 알고리즘은 무한히 분신을 생성하다가 메모리 초과로 뻗는다.

다익스트라로 최단 경로가 아닌 어쨌거나 출구로 갈 수 있는 길 아무거나 하나만 찾고 싶다면 분신 중 하나가 출구에 도착한 순간 해답을 내고 종료하면 된다. 근데 이럴거면 아래쪽의 A*알고리즘이 더 효율적이므로 그걸 쓰는 걸 추천.

만약 모든 에지의 weight값이 같다면 맨 처음 해답을 낸 분신이 최단 경로가 된다.[* 당연하다. 에지의 weight가 모두 같다면 에지를 통과한 수가 가장 적은 탐색자가 가장 짧은 거리를 여행한다. 다익스트라 알고리즘의 타임 스텝은 모든 탐색자가 에지 하나를 통과하는 것이 기준이다.] 또한 좀 꼼수를 써서 분신들로부터 목적지까지 대각선으로 질러가는 남은 거리(장애물을 무시한 직선 거리)를 계산했을 때 현재 계산된 최단 길이를 초과할 경우 소멸하게 만들 수도 있다.[* 거리를 정수로 재는 경우 맨하탄법(X,Y각 축에 사영한 직선 거리를 더하는 방법)으로 재면 정수 거리를 잴 수 있다. 단 각도가 45도에 가까워질수록 오차가 커진다. 그러나 길 자체가 직교밖에 안 하는 미로는 맨하탄법으로도 정확한 거리를 잴 수 있다.] 이렇게 하면 2차원 지도 상에서 탐색 공간의 반지름이 절반으로 줄어든다. 단 이 방법은 weight값에 [[포탈건|음수값]]이 없다는 조건을 만족해야 한다.

부수적인 장점으로 다익스트라 알고리즘은 쉽게 병렬화가 가능하다. GPU같이 코어가 수백 수천개가 집적돼있는 기기에서 다익스트라 알고리즘은 최대의 성능을 발휘한다. 분신 하나당 쓰레드 하나를 생성하는 방식으로 코딩하면 된다. 밑의 A* 알고리즘은 DFS기반이라 어디서 어떻게 쓰레드를 나눌지가 명확하지 않다.

요약

문서 편집을 저장하면 당신은 기여한 내용을 CC BY-NC-SA 2.0 KR 또는 기타 라이선스 (문서에 명시된 경우) 로 배포하고 기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다. 이 동의는 철회할 수 없습니다.

비로그인 상태로 편집합니다. 로그인하지 않은 상태로 문서 편집을 저장하면, 편집 역사에 본인이 사용하는 IP(216.73.216.107) 주소 전체가 영구히 기록됩니다.

미로탐색 알고리즘(r1 문단 편집)

미로탐색 알고리즘_{(r1 문단 편집)}